Attacks by malicious software on digital devices have become one of the most critical issues of the digital age. For example, although many millions of people rely on personal computers (“PCs”) connected to the Internet, those PCs are under constant threat from viruses, worms and other malicious software (known elsewhere and herein as “malware”). Malware is well known to travel to PCs via digital data downloaded from the Internet, but can also propagate to digital devices other than PCs. Malware is known to cause the corruption, theft and/or deletion of digital data from users' devices in both large corporations and homes. Damage from malware is known to be very significant in terms of lost productivity and expense. Lawmakers take the effects of malware seriously and punishment for creators and disseminators of malware can correspondingly even include incarceration.
One of the more significant security lapses exploited by the creators of malware involves an overflow of memory. This occurs when a process attempts to write too much data into a specific memory location within a digital device relative to the amount of memory available. When data written by a legitimate process overflows a memory location, that surplus data can be stored in another, less secure memory location, making the digital device vulnerable to further exploitation. In many digital devices, an operating system's kernel generally tries to prevent one process from accessing data stored by another process in a primary memory location, such as a stack or heap. This problem is exacerbated in a multitasking, multithreaded computing environment where many processes need to store data in the same memory structure, thereby making memory overflows more likely and less predictable.
It is not surprising then that buffer overflows can present one of the largest security problems today for digital devices. There are many ways to overflow a buffer including writing to addresses inside of a loop, sending too small of a buffer to a function call, and incorrect pointer arithmetic, to name a few. The first worm to ever attack the Internet, the Morris worm, was able to do so because of a buffer overflow. The overflow occurred because insufficient memory was allocated before being passed to one of the standard string library functions. Interestingly, the same library function that was used to exploit a program back in 1988 is still in use today.
The problem of buffer overflows has been known even before 1988 and the Morris worm. Since 1965, when the Multics operating system was first conceived, buffer overflows and the threat they pose have been understood. Indeed, one of the main features of the Multics operating system was preventing buffer overflows from occurring. Security was built into the operating system from the start, something most of today's operating systems cannot claim. The same features of memory segmentation provided by the hardware that were found and used in the Burroughs B5700/B6700 Series are still available in some form on the 80×86 Intel architecture. A principle reason overflows still occur is because operating system designers are not taking advantage of the segmentation provided by the underlying hardware. While programmers are quickly realizing that a secure program is more important than a feature rich program, most still view security as an afterthought or something that is addressed in the testing phases.
The main job of an operating system is to provide convenience to the user. Part of that convenience is to protect one process from another, or as stated in A. Silberschatz, P. B. Galvin, and G. Gagne. Operating System Concepts. New York, N.Y., 2003, “ . . . multiple jobs running concurrently require that their ability to affect one another be limited in all phases of the operating system, including process scheduling, disk storage, and memory management.”
The high level C or C++ programming languages enjoy widespread popularity and are perhaps the ones for which most buffer overflow problems arise. When variables are created by a programmer coding in C or C++, they are created in one of three ways. They are created locally in a function and memory is allocated for these variables on the stack, or they are created dynamically via a pointer to memory allocated in the heap, or they can be allocated in the data segment of the executable by declaring them as global or static. Each of these methods for creating variables has its advantages and disadvantages.
Stack allocated variables are created very quickly during run-time by simply decrementing the stack pointer. However, with stack allocated variables, the size of the variable must be known before it is created. When the amount of memory needed is not known during program design the programmer may choose to create memory on the heap. Memory created on the heap can be of virtually any size and is dynamically allocated during run-time. However, this dynamic allocation of memory comes at the cost of needing to run an algorithm to find unallocated chunks of memory large enough for the request. This is one reason why dynamic memory is not used for all variables created in a program. Variables created by the programmer as static or global are stored in the data segment of an executable. The data segment has the advantage that it is created before the process starts executing, therefore, the location never changes. However, memory allocated in the data segment can never be de-allocated, unlike the stack and heap.
Memory is allocated so that data can be written to it. A buffer overflow can potentially occur when any piece of memory is written to. A buffer, or piece of allocated memory, is considered overflowed when the size of the allocated memory is smaller then the amount of data written to it. When a buffer overflow occurs on the stack other information about program execution that is also stored on the stack, can potentially be overwritten. In most cases this causes the program to crash. However, if the data being written was constructed in such a manner as to contain code, then this code could be executed in a disruptive manner on the system. This is a bit different from when a buffer is overflowed in the heap and data segment. Since information about program execution is not normally stored in either of thee locations, the data must be crafted such that it changes the arguments to other functions, making the program execute in a manner not designed by the programmer. More information about what can be done in response to a buffer overflow is described, for example, in Koziol, D. Litchfield, D. Aitel, C. Anley, S. Eren, n. Mehta, and R. Hassel, The Sheilcoder's Handbook: Discovering and exploiting security holes. Wiley Publishing, Inc., Indianapolis, Ind., 2004.
With software becoming ever complex, it only becomes more difficult to detect buffer overflows during the testing phase. The inability of programmers to envision every possible situation their code might experience, or every piece of data that will be written to a buffer in an application is not surprising. Accounting for all situations that might arise when writing a piece of data is virtually impossible, especially when the software is being created by multiple developers.
Currently, there are no known approaches for programmers to check the bounds of any piece of memory before writing data to that memory. The lack of such a method is a deficiency in today's operating systems. Both the compiler and hardware extensions have been suggested in the past as areas where buffer overflows can be trapped after, or identified before, they occur. While these methods do have merit there are inherent problems with each, the biggest problem being that these methods do not provide the programmer with very much, if any, flexibility when dealing with overflows.
Most methods designed for preventing buffer overflows rely on modifications to the compiler. While changing the way data is allocated and memory boundaries of pointers (i.e., pointer bounds) are tracked through the compiler are some of the most obvious and straightforward ways to prevent buffer overflows, they have various limitations. Firstly, all software will need to be recompiled using the new compiler or compiler option. While this may sound trivial it can be a major obstacle to overcome, not just because of its time consuming nature but also because of differences in the way programmers write code.
Secondly, these approaches usually add extra code to an executable and increase the time required to compile a piece of code. It is an indeterminable problem at compile time what bounds need to be checked and which do not. To prevent any buffer from being overflowed all bounds on all buffers would need to be checked, most unnecessarily. This needless checking can add a lot of code to the compiled binary. Any optimizations to try and reduce code bloat due to bounds checking will increase the amount of work performed by the compiler at compile time, thereby increasing compile times.
Thirdly, there is no way to determine if a binary executable has been compiled with such a compiler or not. This presents the problem that people might run binaries on their machines assuming that bounds checking has been previously performed by the compiler when, in fact, it was not. If such a flag were built into the binaries then the operating system would need to be modified so that it could recognize binaries that have not been bounds checked by the compiler and warn the user.
Finally, it is believed that having the compiler check the bounds of buffers will only facilitate the writing of sloppy code. Since the programmer will know the compiler is checking the bounds of buffers, he/she is less inclined to consider it. In the event the compiler cannot catch a certain overflow situation, which is often the case as discovered in R. Jones and P. Kelly. Backwards-compatible bounds checking for arrays and pointers in c programs. Third International Workshop on Automated Debugging, 1997, the programmer will not pay attention to it, and this bug will make it into the final release version of the code.
A known alternative to implementing bounds checking in the compiler is enabling hardware features to do bounds checking, or preventing the adverse effects of buffer overflows once they have occurred. This is what is currently done in most operating systems through the paging system of the Intel 80×86 architecture. However, using the paging system provided by the hardware only prevents against writing to certain pages of memory. The theory behind paging is to aid in the separation of memory between processes, not to enforce bounds of buffers allocated in memory by a single process. This is easily seen because pages do not provide the granularity needed for byte oriented buffers allocated in memory.
Another known approach is to use segmentation of memory through the use of segmentation descriptors. See I. Corporation. Intel Architecture Software Developer's Manual, Volume 3: System Programming. 1999. These segmentation descriptors have the ability to mark pieces of memory as code or data and not allow execution to occur in data sections. While this will prevent the adverse effects of an overflow once it has already happened, it is at a level where only the operating system is able to deal with this problem. While this is enough to prevent a vulnerability by terminating the current process, it does not provide the programmer of that process much chance to recover from such an overflow. It is also important to note that not all buffer overflow situations are caught by simply marking a data segment as non-executable. The only time a fault is generated by the CPU is when such an overflow attempts to set the instruction pointer to an address in a data segment. If this never happens overflows can still occur and cause unexpected results or exploitable results.
Finally, the use of segmentation through hardware can be done for each buffer such that a small space is left in between allocated pieces of memory. This way, if the end of the memory is reached and overwritten it will trigger a fault that the operating system can catch. This has the benefit of being precise to the granularity of each buffer, but has the negative effect of having to waste memory to uphold this boundary between buffers. Also, since a segment descriptor will need to be generated for each allocated piece of memory, the library that allocates the memory will need a way to communicate with the operating system that a buffer is being created and to make a new segment descriptor for it. This would require extensive bookkeeping to be done by the operating system and an even larger cost when allocating a piece of memory on the heap.
The foregoing examples of the related art and their related limitations are intended to be illustrative and not exclusive. Other limitations may become apparent to those practiced in the art upon a reading of the specification and a study of the drawings.